/**
 * @function 前序遍历迭代法，递归顺序:中->左->右，压栈顺序:右->左->中
*/

const preorderTraversal = (root) => {
  const res = [],
    stk = []
  if (root) stk.push(root)
  while (stk.length) {
    const node = stk.pop()
    console.log(stk, 'ssssssssss')
    console.log(node, 'nnnnnnnn')
    if (!node) {
      res.push(stk.pop().val) // 节点出栈
      continue
    }
    if (node.right) stk.push(node.right) // 右节点入栈
    if (node.left) stk.push(node.left) // 左节点入栈
    stk.push(node) // 中间节点入栈
    stk.push(null) // 标记
  }
  return res
}

const root = {
  val: 1,
  left: {
    val: 2,
    left: null,
    right: null
  },
  right: {
    val: 3,
    left: null,
    right: null
  }
}

console.log(preorderTraversal(root));